package org.algorithm.熊猫.数组.三月.第二周;

/**
 * @author 熊猫
 * @date 2022/03/08 11:50 PM
 * @description: 周天作业
 *
 * <p>
 * 给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 * <p>
 * 测试用例的答案是一个32-位 整数。
 * <p>
 * 子数组 是数组的连续子序列。
 * </p>
 * <p>
 * uri:  https://leetcode-cn.com/problems/maximum-product-subarray/
 */
public class 乘积最大子数组 {

    public static void main(String[] args) {
        int[] nums = {-2, 3, -4};
        System.out.println(maxProduct(nums));
    }

    public static int maxProduct(int[] nums) {
        int maxNum = nums[0];
        int minNum = nums[0];
        int result = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; ++i) {
            int mx = maxNum, mn = minNum;
            maxNum = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            minNum = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            result = Math.max(maxNum, result);
        }
        return result;
    }
}
